package com.wwz.leetcode;

import org.junit.Test;

public class LeetCode34 {

    public int[] searchRange(int[] nums, int target) {
        int length = nums.length;
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        if (length == 0) {
            return res;
        }

        int left = 0;
        int right = length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) {
                // 找左边界
                for (int i = 0; i <= mid; i++) {
                    if (mid - i >= left && nums[mid - i] == target) {
                        res[0] = mid - i;
                    }
                }
                // 找右边界
                for (int i = length - 1; i >= 0; i--) {
                    if (mid + i <= length - 1 && nums[mid + i] == target) {
                        res[1] = mid + i;
                        return res;
                    }
                }
            }
            if(nums[mid] < target){
                left = mid+1;
            }
            if(nums[mid] > target){
                right = mid-1;
            }
        }
        return res;
    }


    @Test
    public void test() {
        System.out.println(searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8));
         //System.out.println(searchRange(new int[]{2,2}, 2));

    }

}
